package com.leetcode.partition6;

/**
 * @author `RKC`
 * @date 2021/11/10 15:59
 */
public class LC526优美的排列 {

    public static int countArrangement(int n) {
        int[] dp = new int[1 << n];
        dp[0] = 1;
        //枚举所有的状态
        for (int mask = 1; mask < (1 << n); mask++) {
            int num = Integer.bitCount(mask);
            //遍历mask的每一个数位，并查实把num放在这个数位上，如果满足放入条件，则加入当前结果中
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0 && ((num % (i + 1)) == 0 || (i + 1) % num == 0)) {
                    //mask ^ (1 << i)：将mask的i位置为0，意思就是加上没有取i时的数量
                    dp[mask] += dp[mask ^ (1 << i)];
                }
            }
            System.out.println(Integer.toBinaryString(mask) + "  " + num + "  " + dp[mask]);
        }
        return dp[(1 << n) - 1];
    }

    public static void main(String[] args) {
        System.out.println(countArrangement(4));
    }
}
